#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cstdlib>

using namespace std;

int a[1000005];
int sum[1000005];

int tran(int n)
{
    char tmp[10];
    int sums=0,i;
    itoa(n,tmp,10);
    int len=strlen(tmp);
    for(i=len-1;i>=0;i--)
    {
        sums+=tmp[i]-'0';
    }
    return sums;
}

void dabiao()
{
    int i,j;
    memset(a,-1,sizeof(a));
    //for(i=0;i<=1000000;i++)
    //{
    //    a[i]=i;
    //}
    for (i=2; i<1001; i++)
    {
        for(j=i*i;j<1000000;j+=i)
        {
            a[j]=0;
        }
    }
    sum[0]=sum[1]=0;
    for(i=2;i<=1000000;i++)
    {
        if(a[i]==-1)
        {
            if(a[tran(i)]==-1)
            {
                sum[i]=sum[i-1]+1;
            }else
            {
                sum[i]=sum[i-1];
                //cout<<sum[i]<<endl;
            }
            //cout<<sum[i]<<endl;
        }else
        {
            sum[i]=sum[i-1];
        }
    }

}

int main()
{
    time_t ta,tb;
    int i,c,j,k=0;
    int n,op,ed;
    dabiao();
    cin>>n;
    while(n--)
    {
        k++;
        cin>>op>>ed;
        cout<<"Case #"<<k<<": "<<sum[ed]-sum[op-1]<<endl;
    }
    return 0;
}
